package doing.doing_001_500;

import lombok.*;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 427. Construct Quad Tree 建立四叉树
 * <p>
 * 我们想要使用一棵四叉树来储存一个 N x N 的布尔值网络。网络中每一格的值只会是真或假。
 * 树的根结点代表整个网络。对于每个结点, 它将被分等成四个孩子结点直到这个区域内的值都
 * 是相同的.
 * 每个结点还有另外两个布尔变量: isLeaf 和 val。isLeaf 当这个节点是一个叶子结点时为
 * 真。val 变量储存叶子结点所代表的区域的值。
 * 你的任务是使用一个四叉树表示给定的网络。下面的例子将有助于你理解这个问题：
 * 给定下面这个8 x 8 网络，我们将这样建立一个对应的四叉树：
 * 由上文的定义，它能被这样分割：
 * <p>
 * {1,1,1,1,0,0,0,0},
 * {1,1,1,1,0,0,0,0},
 * {1,1,1,1,1,1,1,1},
 * {1,1,1,1,1,1,1,1},
 * {1,1,1,1,0,0,0,0},
 * {1,1,1,1,0,0,0,0},
 * {1,1,1,1,0,0,0,0},
 * {1,1,1,1,0,0,0,0}
 * <p>
 * 对应的四叉树应该像下面这样，每个结点由一对 (isLeaf, val) 所代表.
 * 对于非叶子结点，val 可以是任意的，所以使用 * 代替。
 * <p>
 * 2019-04-14 6:05 PM
 **/
@SuppressWarnings("all")
public class ConstructQuadTree {

    public Node construct(int[][] grid) {
        return fun(grid, 0, grid[0].length, 0, grid.length);
    }

    public Node fun(int[][] grid, int left, int right, int top, int bottom) {
        int key = grid[top][left];
        for (int i = top; i < bottom; i++) {
            for (int j = left; j < right; j++) {
                if (grid[i][j] != key) {
                    int center = (top + bottom) / 2;
                    int middle = (left + right) / 2;
                    Node topLeft = fun(grid, left, middle, top, center);
                    Node topRight = fun(grid, middle, right, top, center);
                    Node bottomLeft = fun(grid, left, middle, center, bottom);
                    Node bottomRight = fun(grid, middle, right, center, bottom);
                    return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
                }
            }
        }
        Node root = new Node();
        root.val = key == 1 ? true : false;
        root.isLeaf = true;
        return root;
    }

    @Test
    public void test() {
        int[][] grid = new int[][]{{1, 1, 1, 1, 0, 0, 0, 0},
                {1, 1, 1, 1, 0, 0, 0, 0},
                {1, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 0, 0, 0, 0},
                {1, 1, 1, 1, 0, 0, 0, 0},
                {1, 1, 1, 1, 0, 0, 0, 0},
                {1, 1, 1, 1, 0, 0, 0, 0}};
        info("\n{}", construct(grid));
    }
}


@NoArgsConstructor
@AllArgsConstructor
class Node {
    public boolean isLeaf;
    public boolean val;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    @Override
    public String toString() {
        return "root=(\tisLeaf=" + this.isLeaf + ",\tval=" + this.val + "\n" +
                (this.topLeft == null ? "" : ("topLeft=" + this.topLeft)) +
                (this.topRight == null ? "" : ("topRight=" + this.topRight)) +
                (this.bottomLeft == null ? "" : ("bottomLeft=" + this.bottomLeft)) +
                (this.bottomRight == null ? "" : ("bottomRight=" + this.bottomRight));
    }
}

/*
public Node construct(int[][] grid) {
    return fun(grid,0,grid[0].length,0,grid.length);
}

public Node fun(int[][] grid,int left,int right,int top,int bottom){
    Node root = null;
    int key = grid[top][left];
    for(int i=top;i<bottom;i++){
        for(int j=left;j<right;j++){
            if(grid[i][j]!=key){
                Node topLeft = fun(grid,left,(left+right)/2,top,(top+bottom)/2);
                Node topRight = fun(grid,(left+right)/2,right,top,(top+bottom)/2);
                Node bottomLeft = fun(grid,left,(left+right)/2,(top+bottom)/2,bottom);
                Node bottomRight = fun(grid,(left+right)/2,right,(top+bottom)/2,bottom);
                root = new Node(false,false,topLeft,topRight,bottomLeft,bottomRight);
                return root;
            }
        }
    }
    root = new Node();
    root.val = key==1?true:false;
    root.isLeaf = true;
    return root;
}
*/
